Exercise: Scapegoat Trees
Modify the add() method of the scapegoat tree.
We'll cover the following
Task#
Modify the add(x) method of the ScapegoatTree so that it does not waste any time recomputing the sizes of subtrees that have already been computed. This is possible because, by the time the method wants to compute size(w), it has already computed one of size(w.left) or size(w.right).
Sample input
The sample input will be as follows:
5
3
8
1
4
7
9
Expected output
The expected output will be as follows:
Tree contents:
1 3 4 5 7 8 9
Tree after removing 4:
1 3 5 7 8 9
Try it yourself first. If you have trouble getting to the solution, you can move to the solution section to see how to solve the problem. We’ll go through the in-depth solution in the next lesson.
Good luck!
Note: You must implement the method
add()in the below code starting at line 57.
Discussion on Scapegoat Trees
Solution: Scapegoat Trees